The present invention concerns a device for interleaving/deinterleaving digital data. The invention is situated in the field of the transmission of data at a high bit rate, for example audio and/or video signals. A particularly interesting application of the invention concerns the interleaving and/or deinterleaving of data for the coding and decoding of error correcting codes, in particular LDPC (Low Density Parity-Check) codes or turbo codes.
Error correcting codes of the LDPC codes type and turbo codes are well known in the prior art. Reference can be made for example to the prior French patent application FR 2 675 970, which describes the general principle of turbo codes.
These coding and decoding techniques are based on an iterative processing of data, the latter being mixed or interleaved, at each processing step, until a complete decorrelation of any errors that may have been conveyed is obtained. These techniques use an interleaver that performs an iterative permutation of the symbols of an input code.
FIG. 1 depicts the architecture of a known interleaving or deinterleaving device. This device is intended to interleave or deinterleave data delivered by n processing elements, referenced P0 to Pn-1, disposed in parallel, said data representing symbols.
The interleaving or deinterleaving device comprises a set of m memory banks, referenced B0 to Bm-1, disposed in parallel and intended to store data coming from or going to the n processing elements, and an interconnection network INT that is interposed between the processing elements and the memory banks in order at any moment to switch the data from the processing elements to the memory banks or vice versa. The data stored in the memory banks are operands and the results of the processing operations performed in the processing elements. The data to be stored in n of the m memory banks are conventionally generated simultaneously by the n processing elements. Generally, the number m of memory banks is greater than or equal to the number n of processing elements. In the contrary case, the data must be supplied by subset, the size of which is less than or equal to the number of memory banks.
The interconnection network INT and the memory banks are controlled by a dedicated control unit CTRL. More precisely, the control unit is responsible for supplying, at each moment, a command word to the interconnection network and addressing and control sequences to the memory banks in order to access the data in read or write mode. The control unit conventionally comprises a plurality of control memories of the ROM (Read-Only Memory) type and a control circuit for reading the content of these memories.
The control unit conventionally comprises at least one control memory for storing the command words of the interconnection network and a control memory for storing the addressing and control sequences of the memory banks. These sequences and command words depend on the interleaving or deinterleaving rule to be applied, the number n of processing elements, the number m of memory banks, the structure of the interconnection network and the size of the data frames (the number of symbols in the frame) to be processed. In general, the first four parameters, namely the interleaving or deinterleaving rule, the numbers n and m and the structure of the interconnection network, do not vary and are fixed by the equipment comprising the interleaving or deinterleaving device. In particular, the interleaving or deinterleaving rule is imposed by the transmission standard supported by the equipment. The equipment must however be in a position to manage several frame sizes for this standard, typically around a hundred frame sizes or even more. A particular operating mode of the interleaving or deinterleaving device is then associated with each of these frame sizes. For implementation of these various operating modes, the control unit of the interleaving or deinterleaving device generally comprises two control memories for each of the operating modes, namely a so-called network memory for storing the command words for the interconnection network and a so-called access control memory for storing the sequences for addressing and controlling the memory banks for the operating mode in question. As a result the control unit of the device comprises two control memories for each operating mode, the content of these memories generally being computed offline by a memory placement algorithm before being stored therein.
Such interleaving or deinterleaving devices are therefore relatively expensive in terms of surface on silicon since the majority of current and future transmission standards, for example WiMAX (Worldwide Interoperability for Microwave Access) or LTE (Long Term Evolution), are designed to implement several hundreds of operating modes.
Another problem related to the use of this type of interleaving architecture concerns conflict in access to the memory banks B0 to Bm-1. This is because, as can be seen in FIGS. 2 and 3, with this type of architecture, it is possible that two or more processing elements from the elements P0 to Pn-1 producing or using data attempt to write or on the other hand to read different data at the same time in or from the same memory bank. Collisions then occur and, in order to avoid them, it is then necessary to offset or carefully arbitrate accesses to the memory banks, which then slows down the coding or decoding process.
Solutions to this collision problem exist. These consist essentially of modifying the interleaving or deinterleaving rule or introducing elements storing in the interconnection network so that simultaneous accesses to the same memory bank are serialised or find an allocation of the data in the memory banks so that there are no access conflicts. Several techniques have been developed in this regard.
A first family of techniques is based on the definition of an interleaving rule based on one or more regular permutations, for example circular, making it possible to implement an interleaver having a high degree of parallelism with performances equivalent to or better than those of known interleavers, while reducing the complexity of the architecture of the interconnection network, in particular for applications at a very high bit rate. This type of solution also has the advantage of reducing the cost of the control unit by minimising the total number of control memories used. A first technique belonging to this family and called “real turbo codes” is described in detail in the document FR 2 838 581. The drawback of this technique is that it is based on the definition of an interleaving rule that is a priori not consistent with a communication standard. The standards have since changed in order to be based on more or less complex regular permutations making it possible to implement parallel hardware interleavers more easily. Unfortunately, the permutation rules proposed do not make it possible to eliminate all conflicts. This is because memory access conflicts persist for certain parallelisms and/or sizes of frames.
A second family of techniques proposes adding memories in the interconnection network in order to provide a time delay of the data in the event of a conflict situation. This type of approach does however have the drawback of increasing the latency of the circuit and increasing the complexity of the interconnection network. In addition, it is necessary to proceed by simulation in order to determine the sizing of the added memories. One example of a technique of this type is described in the document “SoC-Network for Interleaving in Wireless Communications” by N Wehn, MPSoC, 2004.
A third family of techniques consists of storing the data in memory banks so as to avoid conflicts. This approach consists of identifying the data that are intended to be consumed or produced at the same time in an allocation matrix. Although this family makes it possible to find an assignment of the data in the memory banks that does not give rise to a conflict whatever the interleaving rule, it does however have a certain number of drawbacks. This is because it does not make it possible to generate a memory access that is simple to implement while using simple components in the interconnection network. Moreover, this family requires the use of two control memories per operating mode for storing the natural and interleaved access orders, which further increases the cost of the device.
A first example of a technique belonging to this family is described in the article “Mapping Interleaving Laws to Parallel Turbo-decoder Architectures” by A Tarable, S Benedetto and G Montorsi, IEEE volume 8, March 2004. The approach proposed consists of effecting a first naive allocation of the data in the memory banks, without generating a conflict, and then attributing a memory bank to the non-allocated data while correcting the conflicts by means of a so-called “annealing” or “iterative refinement” method. The simulated annealing algorithm is relatively complex to use and does not make it possible to determine, a priori, the time necessary for obtaining the solution although this time is limited.
A second example is presented in the document FR 2 915 641 entitled “Data interleaving method and device”. This document describes a method for finding, for any interleaving rule, a placement of the data in the memory banks that guarantees conflict-free access to the memories and optimises the interconnection network according to the requirements of the designer if the interleaving rule so permits. With this technique, the control unit is not optimised and its final architecture comprises as many control memories as there are memory banks, for all operating modes to be implemented.